package Leetcode.动态规划;

/**
 * @ClassName 使用最小花费爬楼梯
 * @since: 2023/8/26 15:22
 * @auth: kirito
 * @description:
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 *
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 *
 * 请你计算并返回达到楼梯顶部的最低花费。
 *
 *
 *
 * 示例 1：
 *
 * 输入：cost = [10,15,20]
 * 输出：15
 * 解释：你将从下标为 1 的台阶开始。
 * - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
 * 总花费为 15 。
 * 示例 2：
 *
 * 输入：cost = [1,100,1,1,1,100,1,1,100,1]
 * 输出：6
 * 解释：你将从下标为 0 的台阶开始。
 * - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
 * - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
 * - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
 * 总花费为 6 。
 *
 * dp[i] = Math.min(dp[-1],dp[i-2])
 **/
public class 使用最小花费爬楼梯 {
    public static int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
/*
练练C
#include <stdlib.h>
 int minCostClimbingStairs(int* cost, int costSize) {
   int dp[costSize + 1];
    dp[0] = dp[1] = 0;
    for (int i = 2; i <= costSize; i++) {
        dp[i] = dp[i - 1] + cost[i - 1]< dp[i - 2] + cost[i - 2]?
        dp[i - 1] + cost[i - 1] : dp[i - 2] + cost[i - 2];
    }
    return dp[costSize];
}
int main()
{
    int nums[] = {10, 15, 20};
    int len = sizeof(nums) / 4;
    int ans = minCostClimbingStairs(nums,len);
    printf("%d\n",ans);
    return(0);
}
 */
    public static void main(String[] args) {
        int[] nums = {10, 15, 20};
        System.out.println(minCostClimbingStairs(nums));

    }

}
